class Pair{
    int x;
    int y;

    public Pair(int x, int y){
        this.x = x;
        this.y = y;
    }
}
class Solution {
    public int orangesRotting(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        Queue<Pair> queue = new LinkedList<>();
        
        //遍历矩阵找到所有腐烂橘子
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(grid[i][j] == 2){
                    queue.offer(new Pair(i,j));
                }
            }
        }
        int[][] nextPosition = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
        int step = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            int flag= 0;
            //用当前这一批已经腐烂的橘子带出下一批要腐烂的橘子
            while(size-- != 0){
                Pair curPos = queue.poll();
                for(int i = 0; i < 4; i++){
                    int newX = curPos.x + nextPosition[i][0];
                    int newY = curPos.y + nextPosition[i][1];

                    if(newX < 0 || newX >= row || newY < 0 || newY >= col || grid[newX][newY] != 1){
                        continue;
                    }
                    flag = 1;
                    grid[newX][newY] = 2;
                    queue.offer(new Pair(newX, newY));
                }
            }
            if(flag == 1){
                step++;
            }
        }
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(grid[i][j] == 1){
                    return -1;
                }
            }
        }
        return step;
    }
}